// 1312. 让字符串成为回文串的最少插入次数
// 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
//
// 请你返回让 s 成为回文串的 最少操作次数 。
//
// 「回文串」是正读和反读都相同的字符串。
/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
  const len = s.length
  const dp = new Array(len).fill(0).map(() => new Array(len).fill(0))

  for (let i = 1; i < len; i++) {
    dp[i - 1][i] = (s[i] === s[i - 1]) ? 0 : 1
  }

  for (let i = len - 2; i >= 0; i--) {
    for (let j = i + 1; j < len; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1]
      } else {
        let p1 = dp[i][j - 1] + 1
        let p2 = dp[i + 1][j] + 1
        dp[i][j] = Math.min(p1, p2)
      }
    }
  }

  return dp[0][len - 1]
}

console.log(
  minInsertions(
    'leetcode'
  )
)
